--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
RNS/Cryptography/pure25519/basic.py b2188ce9a746a35b770b10bea1b7ccbe93b4e198 (b2188ce9) Text, 13.06 KB
T8b949e# MIT License
T8b949e#
T8b949e# Copyright (c) 2015 Brian Warner and other contributors
T8b949e# Permission is hereby granted, free of charge, to any person obtaining a copy
T8b949e# of this software and associated documentation files (the "Software"), to deal
T8b949e# in the Software without restriction, including without limitation the rights
T8b949e# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
T8b949e# copies of the Software, and to permit persons to whom the Software is
T8b949e# furnished to do so, subject to the following conditions:
T8b949e#
T8b949e# The above copyright notice and this permission notice shall be included in all
T8b949e# copies or substantial portions of the Software.
T8b949e#
T8b949e# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
T8b949e# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
T8b949e# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
T8b949e# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
T8b949e# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
T8b949e# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
T8b949e# SOFTWARE.
Tff7b72import T7ee787binasciiTff7b72, T7ee787hashlibTff7b72, T7ee787itertools
Te6edf3Q Tff7b72= T79c0ff2Tff7b72*Tff7b72*T79c0ff255 Tff7b72- T79c0ff19
Te6edf3L Tff7b72= T79c0ff2Tff7b72*Tff7b72*T79c0ff252 Tff7b72+ T79c0ff27742317777372353535851937790883648493
Tff7b72def Td2a8ffinvTb4b4b4(Te6edf3xTb4b4b4)Tb4b4b4:
Tff7b72return Tffa657powTb4b4b4(Te6edf3xTb4b4b4, Te6edf3QTff7b72-T79c0ff2Tb4b4b4, Te6edf3QTb4b4b4)
Te6edf3d Tff7b72= Tff7b72-T79c0ff121665 Tff7b72* Te6edf3invTb4b4b4(T79c0ff121666Tb4b4b4)
Te6edf3I Tff7b72= Tffa657powTb4b4b4(T79c0ff2Tb4b4b4,Tb4b4b4(Te6edf3QTff7b72-T79c0ff1Tb4b4b4)Tff7b72/Tff7b72/T79c0ff4Tb4b4b4,Te6edf3QTb4b4b4)
Tff7b72def Td2a8ffxrecoverTb4b4b4(Te6edf3yTb4b4b4)Tb4b4b4:
Te6edf3xx Tff7b72= Tb4b4b4(Te6edf3yTff7b72*Te6edf3yTff7b72-T79c0ff1Tb4b4b4) Tff7b72* Te6edf3invTb4b4b4(Te6edf3dTff7b72*Te6edf3yTff7b72*Te6edf3yTff7b72+T79c0ff1Tb4b4b4)
Te6edf3x Tff7b72= Tffa657powTb4b4b4(Te6edf3xxTb4b4b4,Tb4b4b4(Te6edf3QTff7b72+T79c0ff3Tb4b4b4)Tff7b72/Tff7b72/T79c0ff8Tb4b4b4,Te6edf3QTb4b4b4)
Tff7b72if Tb4b4b4(Te6edf3xTff7b72*Te6edf3x Tff7b72- Te6edf3xxTb4b4b4) Tff7b72% Te6edf3Q Tff7b72!= T79c0ff0Tb4b4b4: Te6edf3x Tff7b72= Tb4b4b4(Te6edf3xTff7b72*Te6edf3ITb4b4b4) Tff7b72% Te6edf3Q
Tff7b72if Te6edf3x Tff7b72% T79c0ff2 Tff7b72!= T79c0ff0Tb4b4b4: Te6edf3x Tff7b72= Te6edf3QTff7b72-Te6edf3x
Tff7b72return Te6edf3x
Te6edf3By Tff7b72= T79c0ff4 Tff7b72* Te6edf3invTb4b4b4(T79c0ff5Tb4b4b4)
Te6edf3Bx Tff7b72= Te6edf3xrecoverTb4b4b4(Te6edf3ByTb4b4b4)
Te6edf3B Tff7b72= Tb4b4b4[Te6edf3Bx Tff7b72% Te6edf3QTb4b4b4,Te6edf3By Tff7b72% Te6edf3QTb4b4b4]
T8b949e# Extended Coordinates: x=X/Z, y=Y/Z, x*y=T/Z
T8b949e# http://www.hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
Tff7b72def Td2a8ffxform_affine_to_extendedTb4b4b4(Te6edf3ptTb4b4b4)Tb4b4b4:
Tb4b4b4(Te6edf3xTb4b4b4, Te6edf3yTb4b4b4) Tff7b72= Te6edf3pt
Tff7b72return Tb4b4b4(Te6edf3xTff7b72%Te6edf3QTb4b4b4, Te6edf3yTff7b72%Te6edf3QTb4b4b4, T79c0ff1Tb4b4b4, Tb4b4b4(Te6edf3xTff7b72*Te6edf3yTb4b4b4)Tff7b72%Te6edf3QTb4b4b4) T8b949e# (X,Y,Z,T)
Tff7b72def Td2a8ffxform_extended_to_affineTb4b4b4(Te6edf3ptTb4b4b4)Tb4b4b4:
Tb4b4b4(Te6edf3xTb4b4b4, Te6edf3yTb4b4b4, Te6edf3zTb4b4b4, Te6edf3_Tb4b4b4) Tff7b72= Te6edf3pt
Tff7b72return Tb4b4b4(Tb4b4b4(Te6edf3xTff7b72*Te6edf3invTb4b4b4(Te6edf3zTb4b4b4)Tb4b4b4)Tff7b72%Te6edf3QTb4b4b4, Tb4b4b4(Te6edf3yTff7b72*Te6edf3invTb4b4b4(Te6edf3zTb4b4b4)Tb4b4b4)Tff7b72%Te6edf3QTb4b4b4)
Tff7b72def Td2a8ffdouble_elementTb4b4b4(Te6edf3ptTb4b4b4)Tb4b4b4: T8b949e# extended->extended
T8b949e# dbl-2008-hwcd
Tb4b4b4(Te6edf3X1Tb4b4b4, Te6edf3Y1Tb4b4b4, Te6edf3Z1Tb4b4b4, Te6edf3_Tb4b4b4) Tff7b72= Te6edf3pt
Te6edf3A Tff7b72= Tb4b4b4(Te6edf3X1Tff7b72*Te6edf3X1Tb4b4b4)
Te6edf3B Tff7b72= Tb4b4b4(Te6edf3Y1Tff7b72*Te6edf3Y1Tb4b4b4)
Te6edf3C Tff7b72= Tb4b4b4(T79c0ff2Tff7b72*Te6edf3Z1Tff7b72*Te6edf3Z1Tb4b4b4)
Te6edf3D Tff7b72= Tb4b4b4(Tff7b72-Te6edf3ATb4b4b4) Tff7b72% Te6edf3Q
Te6edf3J Tff7b72= Tb4b4b4(Te6edf3X1Tff7b72+Te6edf3Y1Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3E Tff7b72= Tb4b4b4(Te6edf3JTff7b72*Te6edf3JTff7b72-Te6edf3ATff7b72-Te6edf3BTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3G Tff7b72= Tb4b4b4(Te6edf3DTff7b72+Te6edf3BTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3F Tff7b72= Tb4b4b4(Te6edf3GTff7b72-Te6edf3CTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3H Tff7b72= Tb4b4b4(Te6edf3DTff7b72-Te6edf3BTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3X3 Tff7b72= Tb4b4b4(Te6edf3ETff7b72*Te6edf3FTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3Y3 Tff7b72= Tb4b4b4(Te6edf3GTff7b72*Te6edf3HTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3Z3 Tff7b72= Tb4b4b4(Te6edf3FTff7b72*Te6edf3GTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3T3 Tff7b72= Tb4b4b4(Te6edf3ETff7b72*Te6edf3HTb4b4b4) Tff7b72% Te6edf3Q
Tff7b72return Tb4b4b4(Te6edf3X3Tb4b4b4, Te6edf3Y3Tb4b4b4, Te6edf3Z3Tb4b4b4, Te6edf3T3Tb4b4b4)
Tff7b72def Td2a8ffadd_elementsTb4b4b4(Te6edf3pt1Tb4b4b4, Te6edf3pt2Tb4b4b4)Tb4b4b4: T8b949e# extended->extended
T8b949e# add-2008-hwcd-3 . Slightly slower than add-2008-hwcd-4, but -3 is
T8b949e# unified, so it's safe for general-purpose addition
Tb4b4b4(Te6edf3X1Tb4b4b4, Te6edf3Y1Tb4b4b4, Te6edf3Z1Tb4b4b4, Te6edf3T1Tb4b4b4) Tff7b72= Te6edf3pt1
Tb4b4b4(Te6edf3X2Tb4b4b4, Te6edf3Y2Tb4b4b4, Te6edf3Z2Tb4b4b4, Te6edf3T2Tb4b4b4) Tff7b72= Te6edf3pt2
Te6edf3A Tff7b72= Tb4b4b4(Tb4b4b4(Te6edf3Y1Tff7b72-Te6edf3X1Tb4b4b4)Tff7b72*Tb4b4b4(Te6edf3Y2Tff7b72-Te6edf3X2Tb4b4b4)Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3B Tff7b72= Tb4b4b4(Tb4b4b4(Te6edf3Y1Tff7b72+Te6edf3X1Tb4b4b4)Tff7b72*Tb4b4b4(Te6edf3Y2Tff7b72+Te6edf3X2Tb4b4b4)Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3C Tff7b72= Te6edf3T1Tff7b72*Tb4b4b4(T79c0ff2Tff7b72*Te6edf3dTb4b4b4)Tff7b72*Te6edf3T2 Tff7b72% Te6edf3Q
Te6edf3D Tff7b72= Te6edf3Z1Tff7b72*T79c0ff2Tff7b72*Te6edf3Z2 Tff7b72% Te6edf3Q
Te6edf3E Tff7b72= Tb4b4b4(Te6edf3BTff7b72-Te6edf3ATb4b4b4) Tff7b72% Te6edf3Q
Te6edf3F Tff7b72= Tb4b4b4(Te6edf3DTff7b72-Te6edf3CTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3G Tff7b72= Tb4b4b4(Te6edf3DTff7b72+Te6edf3CTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3H Tff7b72= Tb4b4b4(Te6edf3BTff7b72+Te6edf3ATb4b4b4) Tff7b72% Te6edf3Q
Te6edf3X3 Tff7b72= Tb4b4b4(Te6edf3ETff7b72*Te6edf3FTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3Y3 Tff7b72= Tb4b4b4(Te6edf3GTff7b72*Te6edf3HTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3T3 Tff7b72= Tb4b4b4(Te6edf3ETff7b72*Te6edf3HTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3Z3 Tff7b72= Tb4b4b4(Te6edf3FTff7b72*Te6edf3GTb4b4b4) Tff7b72% Te6edf3Q
Tff7b72return Tb4b4b4(Te6edf3X3Tb4b4b4, Te6edf3Y3Tb4b4b4, Te6edf3Z3Tb4b4b4, Te6edf3T3Tb4b4b4)
Tff7b72def Td2a8ffscalarmult_element_safe_slowTb4b4b4(Te6edf3ptTb4b4b4, Te6edf3nTb4b4b4)Tb4b4b4:
T8b949e# this form is slightly slower, but tolerates arbitrary points, including
T8b949e# those which are not in the main 1*L subgroup. This includes points of
T8b949e# order 1 (the neutral element Zero), 2, 4, and 8.
Tff7b72assert Te6edf3n Tff7b72>Tff7b72= T79c0ff0
Tff7b72if Te6edf3nTff7b72==T79c0ff0Tb4b4b4:
Tff7b72return Te6edf3xform_affine_to_extendedTb4b4b4(Tb4b4b4(T79c0ff0Tb4b4b4,T79c0ff1Tb4b4b4)Tb4b4b4)
Te6edf3_ Tff7b72= Te6edf3double_elementTb4b4b4(Te6edf3scalarmult_element_safe_slowTb4b4b4(Te6edf3ptTb4b4b4, Te6edf3nTff7b72>>T79c0ff1Tb4b4b4)Tb4b4b4)
Tff7b72return Te6edf3add_elementsTb4b4b4(Te6edf3_Tb4b4b4, Te6edf3ptTb4b4b4) Tff7b72if Te6edf3nTff7b72&T79c0ff1 Tff7b72else Te6edf3_
Tff7b72def Td2a8ff_add_elements_nonunfiedTb4b4b4(Te6edf3pt1Tb4b4b4, Te6edf3pt2Tb4b4b4)Tb4b4b4: T8b949e# extended->extended
T8b949e# add-2008-hwcd-4 : NOT unified, only for pt1!=pt2. About 10% faster than
T8b949e# the (unified) add-2008-hwcd-3, and safe to use inside scalarmult if you
T8b949e# aren't using points of order 1/2/4/8
Tb4b4b4(Te6edf3X1Tb4b4b4, Te6edf3Y1Tb4b4b4, Te6edf3Z1Tb4b4b4, Te6edf3T1Tb4b4b4) Tff7b72= Te6edf3pt1
Tb4b4b4(Te6edf3X2Tb4b4b4, Te6edf3Y2Tb4b4b4, Te6edf3Z2Tb4b4b4, Te6edf3T2Tb4b4b4) Tff7b72= Te6edf3pt2
Te6edf3A Tff7b72= Tb4b4b4(Tb4b4b4(Te6edf3Y1Tff7b72-Te6edf3X1Tb4b4b4)Tff7b72*Tb4b4b4(Te6edf3Y2Tff7b72+Te6edf3X2Tb4b4b4)Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3B Tff7b72= Tb4b4b4(Tb4b4b4(Te6edf3Y1Tff7b72+Te6edf3X1Tb4b4b4)Tff7b72*Tb4b4b4(Te6edf3Y2Tff7b72-Te6edf3X2Tb4b4b4)Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3C Tff7b72= Tb4b4b4(Te6edf3Z1Tff7b72*T79c0ff2Tff7b72*Te6edf3T2Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3D Tff7b72= Tb4b4b4(Te6edf3T1Tff7b72*T79c0ff2Tff7b72*Te6edf3Z2Tb4b4b4) Tff7b72% Te6edf3Q
Te6edf3E Tff7b72= Tb4b4b4(Te6edf3DTff7b72+Te6edf3CTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3F Tff7b72= Tb4b4b4(Te6edf3BTff7b72-Te6edf3ATb4b4b4) Tff7b72% Te6edf3Q
Te6edf3G Tff7b72= Tb4b4b4(Te6edf3BTff7b72+Te6edf3ATb4b4b4) Tff7b72% Te6edf3Q
Te6edf3H Tff7b72= Tb4b4b4(Te6edf3DTff7b72-Te6edf3CTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3X3 Tff7b72= Tb4b4b4(Te6edf3ETff7b72*Te6edf3FTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3Y3 Tff7b72= Tb4b4b4(Te6edf3GTff7b72*Te6edf3HTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3Z3 Tff7b72= Tb4b4b4(Te6edf3FTff7b72*Te6edf3GTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3T3 Tff7b72= Tb4b4b4(Te6edf3ETff7b72*Te6edf3HTb4b4b4) Tff7b72% Te6edf3Q
Tff7b72return Tb4b4b4(Te6edf3X3Tb4b4b4, Te6edf3Y3Tb4b4b4, Te6edf3Z3Tb4b4b4, Te6edf3T3Tb4b4b4)
Tff7b72def Td2a8ffscalarmult_elementTb4b4b4(Te6edf3ptTb4b4b4, Te6edf3nTb4b4b4)Tb4b4b4: T8b949e# extended->extended
T8b949e# This form only works properly when given points that are a member of
T8b949e# the main 1*L subgroup. It will give incorrect answers when called with
T8b949e# the points of order 1/2/4/8, including point Zero. (it will also work
T8b949e# properly when given points of order 2*L/4*L/8*L)
Tff7b72assert Te6edf3n Tff7b72>Tff7b72= T79c0ff0
Tff7b72if Te6edf3nTff7b72==T79c0ff0Tb4b4b4:
Tff7b72return Te6edf3xform_affine_to_extendedTb4b4b4(Tb4b4b4(T79c0ff0Tb4b4b4,T79c0ff1Tb4b4b4)Tb4b4b4)
Te6edf3_ Tff7b72= Te6edf3double_elementTb4b4b4(Te6edf3scalarmult_elementTb4b4b4(Te6edf3ptTb4b4b4, Te6edf3nTff7b72>>T79c0ff1Tb4b4b4)Tb4b4b4)
Tff7b72return Te6edf3_add_elements_nonunfiedTb4b4b4(Te6edf3_Tb4b4b4, Te6edf3ptTb4b4b4) Tff7b72if Te6edf3nTff7b72&T79c0ff1 Tff7b72else Te6edf3_
T8b949e# points are encoded as 32-bytes little-endian, b255 is sign, b2b1b0 are 0
Tff7b72def Td2a8ffencodepointTb4b4b4(Te6edf3PTb4b4b4)Tb4b4b4:
Te6edf3x Tff7b72= Te6edf3PTb4b4b4[T79c0ff0Tb4b4b4]
Te6edf3y Tff7b72= Te6edf3PTb4b4b4[T79c0ff1Tb4b4b4]
T8b949e# MSB of output equals x.b0 (=x&1)
T8b949e# rest of output is little-endian y
Tff7b72assert T79c0ff0 Tff7b72<Tff7b72= Te6edf3y Tff7b72< Tb4b4b4(T79c0ff1Tff7b72<<T79c0ff255Tb4b4b4) T8b949e# always < 0x7fff..ff
Tff7b72if Te6edf3x Tff7b72& T79c0ff1Tb4b4b4:
Te6edf3y Tff7b72+Tff7b72= T79c0ff1Tff7b72<<T79c0ff255
Tff7b72return Te6edf3binasciiTff7b72.Td2a8ffunhexlifyTb4b4b4(Ta5d6ff"Tffd700%064xTa5d6ff" Tff7b72% Te6edf3yTb4b4b4)Tb4b4b4[Tb4b4b4:Tb4b4b4:Tff7b72-T79c0ff1Tb4b4b4]
Tff7b72def Td2a8ffisoncurveTb4b4b4(Te6edf3PTb4b4b4)Tb4b4b4:
Te6edf3x Tff7b72= Te6edf3PTb4b4b4[T79c0ff0Tb4b4b4]
Te6edf3y Tff7b72= Te6edf3PTb4b4b4[T79c0ff1Tb4b4b4]
Tff7b72return Tb4b4b4(Tff7b72-Te6edf3xTff7b72*Te6edf3x Tff7b72+ Te6edf3yTff7b72*Te6edf3y Tff7b72- T79c0ff1 Tff7b72- Te6edf3dTff7b72*Te6edf3xTff7b72*Te6edf3xTff7b72*Te6edf3yTff7b72*Te6edf3yTb4b4b4) Tff7b72% Te6edf3Q Tff7b72== T79c0ff0
Tff7b72class T56d364NotOnCurveTb4b4b4(Tf85149ExceptionTb4b4b4)Tb4b4b4:
Tff7b72pass
Tff7b72def Td2a8ffdecodepointTb4b4b4(Te6edf3sTb4b4b4)Tb4b4b4:
Te6edf3unclamped Tff7b72= Tffa657intTb4b4b4(Te6edf3binasciiTff7b72.Td2a8ffhexlifyTb4b4b4(Te6edf3sTb4b4b4[Tb4b4b4:T79c0ff32Tb4b4b4]Tb4b4b4[Tb4b4b4:Tb4b4b4:Tff7b72-T79c0ff1Tb4b4b4]Tb4b4b4)Tb4b4b4, T79c0ff16Tb4b4b4)
Te6edf3clamp Tff7b72= Tb4b4b4(T79c0ff1 Tff7b72<< T79c0ff255Tb4b4b4) Tff7b72- T79c0ff1
Te6edf3y Tff7b72= Te6edf3unclamped Tff7b72& Te6edf3clamp T8b949e# clear MSB
Te6edf3x Tff7b72= Te6edf3xrecoverTb4b4b4(Te6edf3yTb4b4b4)
Tff7b72if Tffa657boolTb4b4b4(Te6edf3x Tff7b72& T79c0ff1Tb4b4b4) Tff7b72!= Tffa657boolTb4b4b4(Te6edf3unclamped Tff7b72& Tb4b4b4(T79c0ff1Tff7b72<<T79c0ff255Tb4b4b4)Tb4b4b4)Tb4b4b4: Te6edf3x Tff7b72= Te6edf3QTff7b72-Te6edf3x
Te6edf3P Tff7b72= Tb4b4b4[Te6edf3xTb4b4b4,Te6edf3yTb4b4b4]
Tff7b72if Tff7b72not Te6edf3isoncurveTb4b4b4(Te6edf3PTb4b4b4)Tb4b4b4: Tff7b72raise Te6edf3NotOnCurveTb4b4b4(Ta5d6ff"Ta5d6ffdecoding point that is not on curveTa5d6ff"Tb4b4b4)
Tff7b72return Te6edf3P
T8b949e# scalars are encoded as 32-bytes little-endian
Tff7b72def Td2a8ffbytes_to_scalarTb4b4b4(Te6edf3sTb4b4b4)Tb4b4b4:
Tff7b72assert Tffa657lenTb4b4b4(Te6edf3sTb4b4b4) Tff7b72== T79c0ff32Tb4b4b4, Tffa657lenTb4b4b4(Te6edf3sTb4b4b4)
Tff7b72return Tffa657intTb4b4b4(Te6edf3binasciiTff7b72.Td2a8ffhexlifyTb4b4b4(Te6edf3sTb4b4b4[Tb4b4b4:Tb4b4b4:Tff7b72-T79c0ff1Tb4b4b4]Tb4b4b4)Tb4b4b4, T79c0ff16Tb4b4b4)
Tff7b72def Td2a8ffbytes_to_clamped_scalarTb4b4b4(Te6edf3sTb4b4b4)Tb4b4b4:
T8b949e# Ed25519 private keys clamp the scalar to ensure two things:
T8b949e# 1: integer value is in L/2 .. L, to avoid small-logarithm
T8b949e# non-wraparaound
T8b949e# 2: low-order 3 bits are zero, so a small-subgroup attack won't learn
T8b949e# any information
T8b949e# set the top two bits to 01, and the bottom three to 000
Te6edf3a_unclamped Tff7b72= Te6edf3bytes_to_scalarTb4b4b4(Te6edf3sTb4b4b4)
Te6edf3AND_CLAMP Tff7b72= Tb4b4b4(T79c0ff1Tff7b72<<T79c0ff254Tb4b4b4) Tff7b72- T79c0ff1 Tff7b72- T79c0ff7
Te6edf3OR_CLAMP Tff7b72= Tb4b4b4(T79c0ff1Tff7b72<<T79c0ff254Tb4b4b4)
Te6edf3a_clamped Tff7b72= Tb4b4b4(Te6edf3a_unclamped Tff7b72& Te6edf3AND_CLAMPTb4b4b4) Tff7b72| Te6edf3OR_CLAMP
Tff7b72return Te6edf3a_clamped
Tff7b72def Td2a8ffrandom_scalarTb4b4b4(Te6edf3entropy_fTb4b4b4)Tb4b4b4: T8b949e# 0..L-1 inclusive
T8b949e# reduce the bias to a safe level by generating 256 extra bits
Te6edf3oversized Tff7b72= Tffa657intTb4b4b4(Te6edf3binasciiTff7b72.Td2a8ffhexlifyTb4b4b4(Te6edf3entropy_fTb4b4b4(T79c0ff32Tff7b72+T79c0ff32Tb4b4b4)Tb4b4b4)Tb4b4b4, T79c0ff16Tb4b4b4)
Tff7b72return Te6edf3oversized Tff7b72% Te6edf3L
Tff7b72def Td2a8ffpassword_to_scalarTb4b4b4(Te6edf3pwTb4b4b4)Tb4b4b4:
Te6edf3oversized Tff7b72= Te6edf3hashlibTff7b72.Td2a8ffsha512Tb4b4b4(Te6edf3pwTb4b4b4)Tff7b72.Td2a8ffdigestTb4b4b4(Tb4b4b4)
Tff7b72return Tffa657intTb4b4b4(Te6edf3binasciiTff7b72.Td2a8ffhexlifyTb4b4b4(Te6edf3oversizedTb4b4b4)Tb4b4b4, T79c0ff16Tb4b4b4) Tff7b72% Te6edf3L
Tff7b72def Td2a8ffscalar_to_bytesTb4b4b4(Te6edf3yTb4b4b4)Tb4b4b4:
Te6edf3y Tff7b72= Te6edf3y Tff7b72% Te6edf3L
Tff7b72assert T79c0ff0 Tff7b72<Tff7b72= Te6edf3y Tff7b72< T79c0ff2Tff7b72*Tff7b72*T79c0ff256
Tff7b72return Te6edf3binasciiTff7b72.Td2a8ffunhexlifyTb4b4b4(Ta5d6ff"Tffd700%064xTa5d6ff" Tff7b72% Te6edf3yTb4b4b4)Tb4b4b4[Tb4b4b4:Tb4b4b4:Tff7b72-T79c0ff1Tb4b4b4]
T8b949e# Elements, of various orders
Tff7b72def Td2a8ffis_extended_zeroTb4b4b4(Te6edf3XYTZTb4b4b4)Tb4b4b4:
T8b949e# catch Zero
Tb4b4b4(Te6edf3XTb4b4b4, Te6edf3YTb4b4b4, Te6edf3ZTb4b4b4, Te6edf3TTb4b4b4) Tff7b72= Te6edf3XYTZ
Te6edf3Y Tff7b72= Te6edf3Y Tff7b72% Te6edf3Q
Te6edf3Z Tff7b72= Te6edf3Z Tff7b72% Te6edf3Q
Tff7b72if Te6edf3XTff7b72==T79c0ff0 Tff7b72and Te6edf3YTff7b72==Te6edf3Z Tff7b72and Te6edf3YTff7b72!=T79c0ff0Tb4b4b4:
Tff7b72return Tff7b72True
Tff7b72return Tff7b72False
Tff7b72class T56d364ElementOfUnknownGroupTb4b4b4:
T8b949e# This is used for points of order 2,4,8,2*L,4*L,8*L
Tff7b72def Tff7b72__init__Tb4b4b4(Tff7b72selfTb4b4b4, Te6edf3XYTZTb4b4b4)Tb4b4b4:
Tff7b72assert Tffa657isinstanceTb4b4b4(Te6edf3XYTZTb4b4b4, Tffa657tupleTb4b4b4)
Tff7b72assert Tffa657lenTb4b4b4(Te6edf3XYTZTb4b4b4) Tff7b72== T79c0ff4
Tff7b72selfTff7b72.Td2a8ffXYTZ Tff7b72= Te6edf3XYTZ
Tff7b72def Td2a8ffaddTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72if Tff7b72not Tffa657isinstanceTb4b4b4(Te6edf3otherTb4b4b4, Te6edf3ElementOfUnknownGroupTb4b4b4)Tb4b4b4:
Tff7b72raise Tf85149TypeErrorTb4b4b4(Ta5d6ff"Ta5d6ffelements can only be added to other elementsTa5d6ff"Tb4b4b4)
Te6edf3sum_XYTZ Tff7b72= Te6edf3add_elementsTb4b4b4(Tff7b72selfTff7b72.Td2a8ffXYTZTb4b4b4, Te6edf3otherTff7b72.Td2a8ffXYTZTb4b4b4)
Tff7b72if Te6edf3is_extended_zeroTb4b4b4(Te6edf3sum_XYTZTb4b4b4)Tb4b4b4:
Tff7b72return Te6edf3Zero
Tff7b72return Te6edf3ElementOfUnknownGroupTb4b4b4(Te6edf3sum_XYTZTb4b4b4)
Tff7b72def Td2a8ffscalarmultTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3sTb4b4b4)Tb4b4b4:
Tff7b72if Tffa657isinstanceTb4b4b4(Te6edf3sTb4b4b4, Te6edf3ElementOfUnknownGroupTb4b4b4)Tb4b4b4:
Tff7b72raise Tf85149TypeErrorTb4b4b4(Ta5d6ff"Ta5d6ffelements cannot be multiplied togetherTa5d6ff"Tb4b4b4)
Tff7b72assert Te6edf3s Tff7b72>Tff7b72= T79c0ff0
Te6edf3product Tff7b72= Te6edf3scalarmult_element_safe_slowTb4b4b4(Tff7b72selfTff7b72.Td2a8ffXYTZTb4b4b4, Te6edf3sTb4b4b4)
Tff7b72return Te6edf3ElementOfUnknownGroupTb4b4b4(Te6edf3productTb4b4b4)
Tff7b72def Td2a8ffto_bytesTb4b4b4(Tff7b72selfTb4b4b4)Tb4b4b4:
Tff7b72return Te6edf3encodepointTb4b4b4(Te6edf3xform_extended_to_affineTb4b4b4(Tff7b72selfTff7b72.Td2a8ffXYTZTb4b4b4)Tb4b4b4)
Tff7b72def Tff7b72__eq__Tb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72return Tff7b72selfTff7b72.Td2a8ffto_bytesTb4b4b4(Tb4b4b4) Tff7b72== Te6edf3otherTff7b72.Td2a8ffto_bytesTb4b4b4(Tb4b4b4)
Tff7b72def Tff7b72__ne__Tb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72return Tff7b72not Tff7b72self Tff7b72== Te6edf3other
Tff7b72class T56d364ElementTb4b4b4(Te6edf3ElementOfUnknownGroupTb4b4b4)Tb4b4b4:
T8b949e# this only holds elements in the main 1*L subgroup. It never holds Zero,
T8b949e# or elements of order 1/2/4/8, or 2*L/4*L/8*L.
Tff7b72def Td2a8ffaddTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72if Tff7b72not Tffa657isinstanceTb4b4b4(Te6edf3otherTb4b4b4, Te6edf3ElementOfUnknownGroupTb4b4b4)Tb4b4b4:
Tff7b72raise Tf85149TypeErrorTb4b4b4(Ta5d6ff"Ta5d6ffelements can only be added to other elementsTa5d6ff"Tb4b4b4)
Te6edf3sum_element Tff7b72= Te6edf3ElementOfUnknownGroupTff7b72.Td2a8ffaddTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)
Tff7b72if Te6edf3sum_element Tff7b72is Te6edf3ZeroTb4b4b4:
Tff7b72return Te6edf3sum_element
Tff7b72if Tffa657isinstanceTb4b4b4(Te6edf3otherTb4b4b4, Te6edf3ElementTb4b4b4)Tb4b4b4:
T8b949e# adding two subgroup elements results in another subgroup
T8b949e# element, or Zero, and we've already excluded Zero
Tff7b72return Te6edf3ElementTb4b4b4(Te6edf3sum_elementTff7b72.Td2a8ffXYTZTb4b4b4)
T8b949e# not necessarily a subgroup member, so assume not
Tff7b72return Te6edf3sum_element
Tff7b72def Td2a8ffscalarmultTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3sTb4b4b4)Tb4b4b4:
Tff7b72if Tffa657isinstanceTb4b4b4(Te6edf3sTb4b4b4, Te6edf3ElementOfUnknownGroupTb4b4b4)Tb4b4b4:
Tff7b72raise Tf85149TypeErrorTb4b4b4(Ta5d6ff"Ta5d6ffelements cannot be multiplied togetherTa5d6ff"Tb4b4b4)
T8b949e# scalarmult of subgroup members can be done modulo the subgroup
T8b949e# order, and using the faster non-unified function.
Te6edf3s Tff7b72= Te6edf3s Tff7b72% Te6edf3L
T8b949e# scalarmult(s=0) gets you Zero
Tff7b72if Te6edf3s Tff7b72== T79c0ff0Tb4b4b4:
Tff7b72return Te6edf3Zero
T8b949e# scalarmult(s=1) gets you self, which is a subgroup member
T8b949e# scalarmult(s<grouporder) gets you a different subgroup member
Tff7b72return Te6edf3ElementTb4b4b4(Te6edf3scalarmult_elementTb4b4b4(Tff7b72selfTff7b72.Td2a8ffXYTZTb4b4b4, Te6edf3sTb4b4b4)Tb4b4b4)
T8b949e# negation and subtraction only make sense for the main subgroup
Tff7b72def Td2a8ffnegateTb4b4b4(Tff7b72selfTb4b4b4)Tb4b4b4:
T8b949e# slow. Prefer e.scalarmult(-pw) to e.scalarmult(pw).negate()
Tff7b72return Te6edf3ElementTb4b4b4(Te6edf3scalarmult_elementTb4b4b4(Tff7b72selfTff7b72.Td2a8ffXYTZTb4b4b4, Te6edf3LTff7b72-T79c0ff2Tb4b4b4)Tb4b4b4)
Tff7b72def Td2a8ffsubtractTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72return Tff7b72selfTff7b72.Td2a8ffaddTb4b4b4(Te6edf3otherTff7b72.Td2a8ffnegateTb4b4b4(Tb4b4b4)Tb4b4b4)
Tff7b72class T56d364_ZeroElementTb4b4b4(Te6edf3ElementOfUnknownGroupTb4b4b4)Tb4b4b4:
Tff7b72def Td2a8ffaddTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72return Te6edf3other T8b949e# zero+anything = anything
Tff7b72def Td2a8ffscalarmultTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3sTb4b4b4)Tb4b4b4:
Tff7b72return Tff7b72self T8b949e# zero*anything = zero
Tff7b72def Td2a8ffnegateTb4b4b4(Tff7b72selfTb4b4b4)Tb4b4b4:
Tff7b72return Tff7b72self T8b949e# -zero = zero
Tff7b72def Td2a8ffsubtractTb4b4b4(Tff7b72selfTb4b4b4, Te6edf3otherTb4b4b4)Tb4b4b4:
Tff7b72return Tff7b72selfTff7b72.Td2a8ffaddTb4b4b4(Te6edf3otherTff7b72.Td2a8ffnegateTb4b4b4(Tb4b4b4)Tb4b4b4)
Te6edf3Base Tff7b72= Te6edf3ElementTb4b4b4(Te6edf3xform_affine_to_extendedTb4b4b4(Te6edf3BTb4b4b4)Tb4b4b4)
Te6edf3Zero Tff7b72= Te6edf3_ZeroElementTb4b4b4(Te6edf3xform_affine_to_extendedTb4b4b4(Tb4b4b4(T79c0ff0Tb4b4b4,T79c0ff1Tb4b4b4)Tb4b4b4)Tb4b4b4) T8b949e# the neutral (identity) element
Te6edf3_zero_bytes Tff7b72= Te6edf3ZeroTff7b72.Td2a8ffto_bytesTb4b4b4(Tb4b4b4)
Tff7b72def Td2a8ffarbitrary_elementTb4b4b4(Te6edf3seedTb4b4b4)Tb4b4b4: T8b949e# unknown DL
T8b949e# TODO: if we don't need uniformity, maybe use just sha256 here?
Te6edf3hseed Tff7b72= Te6edf3hashlibTff7b72.Td2a8ffsha512Tb4b4b4(Te6edf3seedTb4b4b4)Tff7b72.Td2a8ffdigestTb4b4b4(Tb4b4b4)
Te6edf3y Tff7b72= Tffa657intTb4b4b4(Te6edf3binasciiTff7b72.Td2a8ffhexlifyTb4b4b4(Te6edf3hseedTb4b4b4)Tb4b4b4, T79c0ff16Tb4b4b4) Tff7b72% Te6edf3Q
T8b949e# we try successive Y values until we find a valid point
Tff7b72for Te6edf3plus Tff7b72in Te6edf3itertoolsTff7b72.Td2a8ffcountTb4b4b4(T79c0ff0Tb4b4b4)Tb4b4b4:
Te6edf3y_plus Tff7b72= Tb4b4b4(Te6edf3y Tff7b72+ Te6edf3plusTb4b4b4) Tff7b72% Te6edf3Q
Te6edf3x Tff7b72= Te6edf3xrecoverTb4b4b4(Te6edf3y_plusTb4b4b4)
Te6edf3Pa Tff7b72= Tb4b4b4[Te6edf3xTb4b4b4,Te6edf3y_plusTb4b4b4] T8b949e# no attempt to use both "positive" and "negative" X
T8b949e# only about 50% of Y coordinates map to valid curve points (I think
T8b949e# the other half give you points on the "twist").
Tff7b72if Tff7b72not Te6edf3isoncurveTb4b4b4(Te6edf3PaTb4b4b4)Tb4b4b4:
Tff7b72continue
Te6edf3P Tff7b72= Te6edf3ElementOfUnknownGroupTb4b4b4(Te6edf3xform_affine_to_extendedTb4b4b4(Te6edf3PaTb4b4b4)Tb4b4b4)
T8b949e# even if the point is on our curve, it may not be in our particular
T8b949e# (order=L) subgroup. The curve has order 8*L, so an arbitrary point
T8b949e# could have order 1,2,4,8,1*L,2*L,4*L,8*L (everything which divides
T8b949e# the group order).
T8b949e# [I MAY BE COMPLETELY WRONG ABOUT THIS, but my brief statistical
T8b949e# tests suggest it's not too far off] There are phi(x) points with
T8b949e# order x, so:
T8b949e# 1 element of order 1: [(x=0,y=1)=Zero]
T8b949e# 1 element of order 2 [(x=0,y=-1)]
T8b949e# 2 elements of order 4
T8b949e# 4 elements of order 8
T8b949e# L-1 elements of order L (including Base)
T8b949e# L-1 elements of order 2*L
T8b949e# 2*(L-1) elements of order 4*L
T8b949e# 4*(L-1) elements of order 8*L
T8b949e# So 50% of random points will have order 8*L, 25% will have order
T8b949e# 4*L, 13% order 2*L, and 13% will have our desired order 1*L (and a
T8b949e# vanishingly small fraction will have 1/2/4/8). If we multiply any
T8b949e# of the 8*L points by 2, we're sure to get an 4*L point (and
T8b949e# multiplying a 4*L point by 2 gives us a 2*L point, and so on).
T8b949e# Multiplying a 1*L point by 2 gives us a different 1*L point. So
T8b949e# multiplying by 8 gets us from almost any point into a uniform point
T8b949e# on the correct 1*L subgroup.
Te6edf3P8 Tff7b72= Te6edf3PTff7b72.Td2a8ffscalarmultTb4b4b4(T79c0ff8Tb4b4b4)
T8b949e# if we got really unlucky and picked one of the 8 low-order points,
T8b949e# multiplying by 8 will get us to the identity (Zero), which we check
T8b949e# for explicitly.
Tff7b72if Te6edf3is_extended_zeroTb4b4b4(Te6edf3P8Tff7b72.Td2a8ffXYTZTb4b4b4)Tb4b4b4:
Tff7b72continue
T8b949e# Test that we're finally in the right group. We want to scalarmult
T8b949e# by L, and we want to *not* use the trick in Group.scalarmult()
T8b949e# which does x%L, because that would bypass the check we care about.
T8b949e# P is still an _ElementOfUnknownGroup, which doesn't use x%L because
T8b949e# that's not correct for points outside the main group.
Tff7b72assert Te6edf3is_extended_zeroTb4b4b4(Te6edf3P8Tff7b72.Td2a8ffscalarmultTb4b4b4(Te6edf3LTb4b4b4)Tff7b72.Td2a8ffXYTZTb4b4b4)
Tff7b72return Te6edf3ElementTb4b4b4(Te6edf3P8Tff7b72.Td2a8ffXYTZTb4b4b4)
T8b949e# never reached
Tff7b72def Td2a8ffbytes_to_unknown_group_elementTb4b4b4(Tffa657bytesTb4b4b4)Tb4b4b4:
T8b949e# this accepts all elements, including Zero and wrong-subgroup ones
Tff7b72if Tffa657bytes Tff7b72== Te6edf3_zero_bytesTb4b4b4:
Tff7b72return Te6edf3Zero
Te6edf3XYTZ Tff7b72= Te6edf3xform_affine_to_extendedTb4b4b4(Te6edf3decodepointTb4b4b4(Tffa657bytesTb4b4b4)Tb4b4b4)
Tff7b72return Te6edf3ElementOfUnknownGroupTb4b4b4(Te6edf3XYTZTb4b4b4)
Tff7b72def Td2a8ffbytes_to_elementTb4b4b4(Tffa657bytesTb4b4b4)Tb4b4b4:
T8b949e# this strictly only accepts elements in the right subgroup
Te6edf3P Tff7b72= Te6edf3bytes_to_unknown_group_elementTb4b4b4(Tffa657bytesTb4b4b4)
Tff7b72if Te6edf3P Tff7b72is Te6edf3ZeroTb4b4b4:
Tff7b72raise Tf85149ValueErrorTb4b4b4(Ta5d6ff"Ta5d6ffelement was ZeroTa5d6ff"Tb4b4b4)
Tff7b72if Tff7b72not Te6edf3is_extended_zeroTb4b4b4(Te6edf3PTff7b72.Td2a8ffscalarmultTb4b4b4(Te6edf3LTb4b4b4)Tff7b72.Td2a8ffXYTZTb4b4b4)Tb4b4b4:
Tff7b72raise Tf85149ValueErrorTb4b4b4(Ta5d6ff"Ta5d6ffelement is not in the right groupTa5d6ff"Tb4b4b4)
T8b949e# the point is in the expected 1*L subgroup, not in the 2/4/8 groups,
T8b949e# or in the 2*L/4*L/8*L groups. Promote it to a correct-group Element.
Tff7b72return Te6edf3ElementTb4b4b4(Te6edf3PTff7b72.Td2a8ffXYTZTb4b4b4)
──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────